import java.util.Stack;

/**
 * 394. 字符串解码
 * https://leetcode.cn/problems/decode-string/description/
 */
class Solution {
    public String decodeString(String s) {
        char[] ch = s.toCharArray();
        Stack<Integer> op = new Stack();
        Stack<StringBuffer> str = new Stack();
        str.push(new StringBuffer(""));
        int i = 0, n = s.length();

        while(i < n) {
            if(ch[i] >= '1' && ch[i] <= '9') {
                //1、遇到数字：提取出这个数字，放入“数字栈”中
                int tmp = ch[i] - '0';
                while(i + 1 < n && ch[i+1] >= '0' && ch[i+1] <= '9') {
                    tmp = tmp * 10 + (ch[i+1] - '0');
                    i++;
                }
                op.push(tmp);
            } else if(ch[i] == '[') {
                //2、遇到'['：把后面的字符串提取出来，放入“字符串栈”中
                StringBuffer tmp = new StringBuffer();
                while(i + 1 < n && ch[i + 1] >= 'a' && ch[i + 1] <= 'z') {
                    tmp.append(ch[i + 1]);
                    i++;
                }
                str.push(tmp);
            } else if(ch[i] == ']') {
                //3、遇到']'：解析，然后方法哦“字符串栈”栈顶的字符串后面
                StringBuffer cur = str.pop();
                StringBuffer tmp = new StringBuffer();
                int m = op.pop();
                for(int j = 0; j < m; j++) {
                    tmp.append(cur);
                }
                str.push(str.pop().append(tmp));
            } else{
                //4、遇到单独的字符：提取出来这个字符串，直接放在“字符串栈”栈顶的字符串后面
                StringBuffer tmp = new StringBuffer();
                tmp.append(ch[i]);
                while(i + 1 < n && ch[i + 1] >= 'a' && ch[i + 1] <= 'z') {
                    tmp.append(ch[i + 1]);
                    i++;
                }
                str.push(str.pop().append(tmp));
            }
            i++;
        }
        return str.pop().toString();
    }
}